// 给定一个二叉树，设计算法原地将它展开为一个单链表（以右链展开）。

function flatten(root: TreeNode | null): void {
    while (root) {
        if (root.left) {// 当前节点存在左子树时
            // 储存左右子树
            let leftTree: TreeNode = root.left;
            let rightTree: TreeNode | null = root.right;
            // 寻找左子树上的连接点
            let connectPoint: TreeNode = root.left;
            while (connectPoint.right) {
                connectPoint = connectPoint.right;
            }
            connectPoint.right = rightTree;// 连接点的右子树赋值为当前节点右子树
            root.right = leftTree;// 当前节点右子树赋值为当前节点左子树
            root.left = null;// 当前节点左子树置空
            root = root.right;
        } else {// 当前节点不存在左子树时，继续往右子树遍历
            root = root.right;
        }
    }
};


// 这道题目也是一道经典的值得反复练习的例题
// 题目的难点在于需要原地完成二叉树对链表转换的操作
// 采用画图的方式配合可以利于更加直观的理解
// 题目中要求的是以右链进行展开，展开顺序实质上就是二叉树的先序遍历结果
// 完成这些操作需要严格按照下列顺序来进行操作
// 当前节点存在左子树时：
// 1、寻找连接点，连接点为当前节点左子树的最右节点
// 2、找到连接点后，将连接点的右子树赋值为当前节点的右子树
// 3、回到当前节点，当前节点的右子树赋值为当前节点的左子树
// 4、所有操作做完后别忘为当前的左子树置空
// 而若当前节点不存在左子树时，继续往右子树遍历即可，
// 理想情况下二叉树上不存在任意的左子树那么它就是一个以右链展开的单链表

